
#ifndef GRAPH_UNIONFINDSET_H
#define GRAPH_UNIONFINDSET_H

//          并查集
//     在此用于是为Kruskal最小生成树算法服务
//     在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。
//     开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。
//     在此过程中要反复用到查询某一个元素归属于那个集合的运算。
//     这种时候就适用并查集

#include <algorithm>
#include <vector>
#include <map>

using namespace std;

// 如果下标无法对应的话，这样处理
//template<class T>
//class UnionFindSet
//{
//public:
//    UnionFindSet(const T* a, size_t n)
//    {
//        for (size_t i = 0 ; i < n ; i++) {
//            _a.push_back(a[i]);
//            _indexMap[a[i]] = i;
//        }
//    }
//private:
//    vector<T> _a; // 编号找人
//    map<T, int> _indexMap;// 人找编号
//};


//1. 数组的下标对应集合中元素的编号
//2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数
//3. 数组中如果为非负数，代表该元素双亲在数组中的下标
class UnionFindSet
{
public:
    // 初始时，将数组中元素全部设置为-1
    UnionFindSet(size_t n)
        :_ufs(n, -1)
    {}

    // 合并两个集合
    void Union(int x1, int x2)
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

        // 如果本身就在一个集合，那么无需合并
        if (root1 == root2) return ;

        // 合并的时候，作为孩子，其深度会增加一层
        // 因此，理论上来说，数据量小的作孩子
        // 如果有需求下标小的作根，则交换一下root
        // if (root1 > root2) swap(root1, root2); // 按照下标大小
        if (abs(_ufs[root1]) < abs(_ufs[root2])) swap(root1, root2); // 按照数据量大小

        // 如果不在同一个集合，则默认认为把x2代表集合合并到x1上，即x1作根，x2作子
        _ufs[root1] += _ufs[root2];

        // 将x2代表集合的名称改为x1
        _ufs[root2] = root1;
    }

    // 给一个元素的编号，找到该元素所在集合的名称
    int FindRoot(int x)
    {
        int root = x;
        while (_ufs[root] >= 0){
            root = _ufs[root];
        }

        // 路径压缩，用于应对深度太深的情况
        // 把路径上所有节点都作为根的孩子
        while (_ufs[x] >= 0){
            int parent = _ufs[x];
            _ufs[x] = root;
            x = parent;
        }

        return root;
    }

    // 判断是不是在同一个集合
    bool isInset(int x1, int x2)
    {
        return FindRoot(x1) == FindRoot(x2);
    }

    // 计算一下有几个集合（树）
    size_t SetSize()
    {
        size_t size = 0;
        for (size_t i = 0 ; i < _ufs.size() ; i++){
            if (_ufs[i] < 0) size++;
        }

        return size;
    }
private:
    vector<int> _ufs; // 假设给的就是下标
};

#endif //GRAPH_UNIONFINDSET_H
